\chapter{Fundamentação Teórica} \label{chap:fundamentacao}

Este capítulo tem por objetivo fornecer ao leitor uma visão geral dos fundamentos  e  
conceitos necessários para o entendimento da metodologia desenvolvida neste trabalho.

Em um primeiro momento serão introduzidos os fundamentos em processamento de imagens, tais
como aquisição e formas de representação. Depois serão apresentados as métricas a serem 
utilizadas para avaliação do desempenho. Na sequência, serão explicados conceitos 
relacionados à histogramas e métodos de comparação dos mesmos. Por fim, serão abordados
conhecimentos associados à redes neurais artificiais.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Aquisição de Imagens Digitais} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Podemos definir uma imagem como uma função $f(x,y)$ de duas variáveis, onde $x$ e $y$ representam um 
uma coordenada em um plano e o valor de $f(x, y)$ corresponde a intensidade luminosa~\cite{Gonzalez}. 
Tratando-se dos computadores digitais atuais, dispomos de uma quantidade limitada de bits 
para a representação de infinitas quantias.
Portanto, apenas quando os valores de $x$, $y$ e $f(x, y)$ são discretos, dizemos que $f(x, y)$ 
representa uma imagem digital. 
Uma imagem digital pode ser vista matematicamente como uma matriz 
$M\times N$ com $M$ linhas e $N$ colunas sendo que, a cada elemento desta matriz, 
dá-se o nome de píxel.

Existem vários possíveis modelos de representação de cores~\cite{Oge} para imagens digitais, vários deles orientados a \textit{hardware} 
(impressoras ou monitores coloridos, por exemplo). Por simplicidade, entretanto, serão consideradas, nesta Seção de Aquisição, 
apenas imagens níveis de cinza, já que os conceitos podem ser facilemente extendidos aos outros modelos. Representações coloridas
serão comentadas na próxima Seção  (\ref{sec:representacao} Representação de Imagens Digitais).

A primeira etapa do processamento de imagens é a aquisição. Os objetos de uma cena refletem a energia luminosa de uma fonte de 
luz e sensibilizam os sensores de algum dispositivo, nos fornecendo informações sobre uma paisagem.  Cada sensor responde com um sinal
elétrico de intensidade proporcional a quantidade luminosa recebida~\cite{Bovik}. Uma câmera fotográfica digital é um exemplo deste tipo de 
dispositivo e normalmente possui um um arranjo de sensores na forma de matriz~\cite{Gonzalez}. 


Para uma análise computacional, devemos transformar os elementos obtidos pelos sensores em números representáveis digitalmente~\cite{Castleman}.
Portanto, é necessário aplicar ao sinal elétrico que representa a imagem processos de amostragem e quantização.

\subsection{Amostragem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

A Figura~\ref{fig:sampling} retrata a ideia da amostragem. Queremos converter a função $f(x, y)$ contínua para a sua versão digital (discreta),
nesta etapa, nos preocupamos apenas com os valores presentes no domínio da função.
Basta, então, que peguemos algumas amostras do sinal em quantidade suficiente para manter 
suas características principais. Na Figura~\ref{fig:sampling}, 
se considerarmos as pequenas variações da função como ruído,
podemos observar que os valores amostrados, indicados pelos quadrados brancos,
representam satisfatoriamente a forma geral da função original, 
mas alguns detalhes são perdidos, de forma que não
será possível recuperar toda a informação da função. 

\begin{figure}[H]
	\centering
	\includegraphics[width=0.6\textwidth]{imagens/capitulo2/sampling}
	\caption[Amostragem.]{Amostragem~\cite{Gonzalez}.}
	\label{fig:sampling}
\end{figure}

Entretanto, no contexto de imagens, estamos normalmente mais interessados na 
informação visual, permitindo-nos a perda de elementos que farão pouca diferença na imagem como um todo.

A chamada frequência de Nyquist nos diz o limite inferior de amostras que devemos obter para que 
possamos manter as informações do sinal, fornecendo-nos um embasamento matemático para o processo de amostragem~\cite{Bovik}.
Utilizando a frequência de Nyquist nenhuma informação do sinal é perdida.

Uma imagem amostrada pode ser vista basicamente como um vetor de números, de tamanho finito (que é o objetivo principal do processo),
cada um representando um píxel da imagem.

\subsection{Quantização}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Após a amostragem, realiza-se a quantização do sinal. Novamente, o processo será explicado
apenas para tons de cinza, uma vez que a extensão do método para outras representações é análoga.
Lembrando que os valores 
de $f(x, y)$ representam as intensidades luminosas de cada píxel, o
processo de quantização consiste em definir a quantidade de bits disponíveis para a
representação (níveis de cinza) e associar os valores contínuos de $f(x, y)$ a um 
valor discreto, um determinado nível de cinza. Geralmente se utiliza 256 níveis para cada componente.

%Ao contrário da amostragem, não existe uma fórmula matemática que demonstre 
%um limite inferior para a quantização. Por este motivo, 
%torna-se mais complexa a tarefa de avaliar matematicamente se determinada 
%quantidade de níveis de cinza é adequada, apesar de as diferenças
%visuais serem claras~\cite{Bovik}.

A Figura~\ref{fig:sample_and_quantization} apresenta um exemplo de 
uma imagem analógica que foi digitalizada (após ter passado pelos processos de  amostragem 
e quantização). 

\begin{figure}[H]
	\centering
	\includegraphics[width=0.7\textwidth]{imagens/capitulo2/sample_and_quantization}
	\caption[Amostragem e Quantização.]{Amostragem e Quantização~\cite{Gonzalez}.}
	\label{fig:sample_and_quantization}
\end{figure}

Nota-se claramente a perda resultante do processo. A imagem mantém o aspecto geral, mas 
perde informações tanto devido ao tamanho dos blocos quanto pelos níveis
de cinza utilizados.

Apesar das limitações, o aumento da qualidade dos recursos disponíveis 
nos dispositivos tende a tornar estes desvios 
imperceptíveis aos usuários, mesmo porque a percepção do olho humano é limitada.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section {Representação de Imagens Digitais} \label{sec:representacao} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection {Formas de Representação}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

O resultado da amostragem e quantização é uma matriz de números. Convenciona-se a origem dos eixos
como sendo o canto superior esquerdo da imagem, que é representada pela referida matriz.
Cada elemento da matriz é denominado píxel. Devemos ressaltar também que os píxeis
encontram-se em número finito e são igualmente espaçados em uma imagem digital. A 
Figura~\ref{fig:representacao_imgs} exemplifica a representação.

Podemos utilizar a seguinte notação matemática:

\begin{equation}
  f(x,y)=
  \begin{bmatrix}
    f(0,0) & f(0,1) & ... & f(0,N-1)\\ 
    f(1,0) & f(1,1) & ... & f(0,N-1)\\
    ... & ... & ... & ...\\
    f(M-1,0) & f(M-1,1) & ... & f(M-1,N-1)
  \end{bmatrix}
\end{equation}

Alternativamente,

\begin{equation}
  A_{i,j}=
  \begin{bmatrix}
    a_{0,0} & a_{0,1} & ... & a_{0,N-1}\\ 
    a_{1,0} & a_{1,1} & ... & a_{0,N-1}\\
    ... & ... & ... & ...\\
    a_{M-1,0} & a_{M-1,1} & ... & a_{M-1,N-1}
  \end{bmatrix}
\end{equation}

Os valores para $M$ e $N$  são escolhidos de acordo com o 
equipamento utilizado e as necessidades da aplicação. Os valores $A_{i,j}$ também são obtidos 
durante o processo de digitalização e representam, por exemplo,
a quantidade de níveis de cinza. 

\begin{figure}[H]
	\centering
	\includegraphics[width=0.65\textwidth]{imagens/capitulo2/representacao_imgs}
	\caption[Representação de imagens digitais.]{Representação de imagens digitais~\cite{Gonzalez}.}
	\label{fig:representacao_imgs}
\end{figure}

No que tange às cores, existem inúmeras formas de representação. 
Nos tópicos que seguem, serão consideradas algumas das maneiras mais comuns, visto que a utilização de uma ou 
outra representação pode trazer benefícios e tornar o processamento mais simples em situações 
específicas. Neste trabalho, serão abordados os seguintes tipos de imagens: 

\begin{itemize}
  \item Binárias;
  \item Escala de cinza;
  \item RGB;
  \item YCbCr.
\end{itemize}

\subsection {Representação Binária}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Este é o caso mais simples, onde $f(x,y)$ assume apenas os valores 0 ou 1 (comumente branco e preto, respectivamente).
Apesar de limitada, esta representação é extremamente compacta: é necessário apenas 1 bit por píxel.
Algumas aplicações interessantes que podem ser mencionadas são a representação de textos, partituras, etc..

\begin{figure}[H]
	\centering
	\includegraphics[width=0.65\textwidth]{imagens/capitulo2/partitura}
	\caption{Partitura com representação binária de cores.}
	\label{fig:partitura}
\end{figure}

\subsection {Representação em Escala de Cinza}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Por escala de cinza entendemos que a imagem possuirá apenas tons de cinza que variam entre o preto e o branco.
A Figura~\ref{fig:peppers} ilustra uma imagem colorida e sua respectiva versão em escalas de cinza.

\begin{figure}[H]
	\includegraphics[width=0.5\textwidth]{imagens/capitulo2/peppers}
	\includegraphics[width=0.5\textwidth]{imagens/capitulo2/peppers_gray}
	\caption{(a) Imagem em escala de cinza (8 bits) e (b) imagem original.}
	\label{fig:peppers}
\end{figure}

Seja $L$ o número de níveis de cinza (tons) e sabendo que
comumente são utilizados 8 bits por píxel, temos $L = 2^8 = 256$ níveis de brilho como padrão. 
Desta maneira, o número de bits necessários
para se representar a imagem pode ser obtido pela fórmula:

\begin{equation}
  N_{bits} = M*N*L
\end{equation}

Vale ressaltar que o número de bits por píxel pode ser alterado de acordo 
com as necessidades, caso haja suporte do sistema.
Se utilizássemos 10 bits, por exemplo, teríamos $L = 2^{10} = 1024$ níveis de cinza.

\subsection {Representação RGB} \label{sub:rgb}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

RGB é uma sigla do inglês que significa \textit{Red, Green, Blue} ou respectivamente Vermelho, Verde e Azul,
sendo que cada letra designa uma de suas componentes. A sobreposição de cada uma destas compontenes gera a cor final.
Trata-se de um dos formatos mais simples e um dos primeiros padrões para imagens coloridas.
As Figuras~\ref{fig:lena} e ~\ref{fig:lena_rgb} apresentam a imagem original e as suas respectivas componentes.  

\begin{figure}[H]
	\centering
	\includegraphics[width=0.5\textwidth]{imagens/capitulo2/lena}
	\caption{Imagem original.}
	\label{fig:lena}
\end{figure}

\begin{figure}[H]
	\includegraphics[width=0.32\textwidth]{imagens/capitulo2/lena_r}
	\includegraphics[width=0.32\textwidth]{imagens/capitulo2/lena_g}
	\includegraphics[width=0.32\textwidth]{imagens/capitulo2/lena_b}
	\caption{Na sequência, componentes (a) vermelha, (b) verde e (c) azul.}
	\label{fig:lena_rgb}
\end{figure}
 
Assim como no caso das imagens em escala de cinza, assumiremos como padrão o valor de 8 bits por píxel (em cada componente RGB).
Da mesma maneira, este número é o mais comum, mas não existe nenhum impedimento para a utilização de uma outra
quantidade de bits. 

\subsection {Representação YCbCr} \label{sub:ycbcr}

O olho humano possui uma sensibilidade maior ao brilho (também chamado de luminância) do que à cor 
(também chamada de crominância). O YCbCr é uma forma de representação que visa tirar proveito deste fato,
visto que o RGB não o faz.

A componente Y armazena uma maior quantidade de informações de luminância~\cite{Vezhnevets03asurvey}.
Em contrapartida, a esta componente tende a sofrer maiores variações causadas por diferentes condições
climáticas, diferentes dispositivos, entre outros. De maneira contrária, as componentes Cb e Cr, 
por armazenarem informações cromáticas, tendem a apresentar menos variações        .
Por estes motivos, podemos concentrar nossos 
esforços alternativamente na luminância ou na crominância, dependendo dos nossos objetivos.

\begin{figure}[H]
	\centering
	\includegraphics[width=0.49\textwidth]{imagens/capitulo2/office}
	\caption{Imagem original.}
	\label{fig:lena}
\end{figure}
\begin{figure}[H]
	\includegraphics[width=0.32\textwidth]{imagens/capitulo2/office_y}
	\includegraphics[width=0.32\textwidth]{imagens/capitulo2/office_cb}
	\includegraphics[width=0.32\textwidth]{imagens/capitulo2/office_cr}
	\caption{Na sequência, (a) componente Y, (b) componente Cb e (c) componente Cr.}
	\label{fig:office}
\end{figure}

Pode ser útil também saber como são realizadas as transformações entre os espaços de cores RGB e YCbCr,
que se dão através das seguintes fórmulas:
\begin{itemize}
 \item De RGB para YCbCr
    \begin{equation}
      Y = 0,299R + 0,857G + 0,114B
    \end{equation}
    \begin{equation}
      Cb = 0,564(R-Y)
    \end{equation}
    \begin{equation}
      CR = 0,713(R-Y)
    \end{equation}
 \item De YCbCr para RGB
    \begin{equation}
      R = Y + 1,402Cr
    \end{equation}
    \begin{equation}
      G = Y - 0,344Cb -0,714Cr
    \end{equation}
    \begin{equation}
      B = Y + 1,772Cb
    \end{equation}
\end{itemize}





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section {Acurácia} \label{sec:acuracia} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

A acurácia é uma medida que representa a probabilidade de acerto de um sistema binário.
É uma relação entre todas as respostas corretas retornadas pelo sistema e 
o total de respostas, sendo definido da seguinte forma:

\begin{equation}
    \textit{Acurácia} = \frac{TP+TN}{TP+TN+FP+FN}
\end{equation}

Onde as medidas $TP$, $FP$, $TN$ e $FN$ são respectivamente, verdadeiro-positivo, 
falso-positivo, verdadeiro-negativo e falso-negativo. Estes valores podem ser 
calculados utilizando a matriz de confusão da Figura~\ref{fig:foto_e_histograma}.

\begin{figure}[H]
	\centering
	\includegraphics[width=0.6\textwidth]{imagens/capitulo2/matriz_confusao}
	\label{fig:foto_e_histograma}
\end{figure}

Ou seja, 
$TP$ são as ocorrências que pertencem à classe e foram classificadas corretamente,
$FP$ são as ocorrências que não pertencem à classe e foram classificadas como pertencentes à classe,
$TN$ são as ocorrências que não pertencem à classe e foram classificadas como não pertencentes à classe e 
$FN$ são as ocorrências que pertencem à classe e foram classificadas como não pertencentes à classe.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section {\textit{F-measure}} \label{sec:fmeasure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

A \textit{F-measure} é média harmônica das medidas \textit{precision} e \textit{recall}.

\begin{equation}
    F\textrm{-}measure = 2 \cdot \frac{precision \times recall}{precision + recall}
\end{equation}

Onde \textit{precision} e \textit{recall} são definidas por:

\begin{equation}
    precision = \frac{TP}{TP + FP}
\end{equation}

\begin{equation}
    recall = \frac{TP}{TP + FN}
\end{equation}

A \textit{precision} representa a probabilidade de uma classificação retornada pelo sistema 
como positiva ser uma ocorrência verdadeiramente positiva ($TP$). Ela é a relação entre a quantidade
de classificações verdadeiramente positivas e a quantidade total de classificações
retornadas como positivas ($TP+FP$).

A medida \textit{recall} calcula a probabilidade de uma ocorrência verdadeiramente
positiva ($TP$) ser classificada como tal. Ela é a relação entre a quantidade de classificações
verdadeiramente positivas e a quantidade total de ocorrências que deveriam
ter sido classificadas como positivas ($TP+FN$).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section {Histogramas} \label{sec:histograma}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection {Definição de Histograma}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

O histograma~\cite{Pearson1895ab} é uma ferramenta estatística para representação visual da distribuição dos dados.
Ele consiste de um gráfico de barras verticais no qual o eixo horizontal representa os baldes (intervalos
discretos, também conhecidos como \textit{bins}, em inglês) e o eixo vertical representa o a frequência de ocorrência 
dos dados em cada um dos baldes. A análise de histogramas pode indicar, por exemplo, 
se os dados se aproximam de uma distribuição normal.

Os intervalos (baldes) são sequenciais e normalmente possuem o mesmo tamanho. Deve-se notar que quando o número de baldes 
tende ao infinito (ou os intervalos tendem a zero), a distribuição de frequência passa a ser uma distribuição de densidade 
de probabilidades. Em ambos os casos, a área do gráfico representa o número total de amostras de dados.
A Figura~\ref{fig:foto_e_histograma} exemplifica um histograma.

\begin{figure}[H]
	\centering
	\includegraphics[width=0.4\textwidth]{imagens/capitulo2/cameraman}
	\includegraphics[width=0.5\textwidth]{imagens/capitulo2/histograma_fotografo}
	\caption{Imagem \textit{cameraman} e seu respectivo histograma.}
	\label{fig:foto_e_histograma}
\end{figure}

A foto da Figura~\ref{fig:foto_e_histograma} possui tamanho 256x256 píxeis, cada qual com 256 níveis de cinza. Para a 
formulação do histograma foram utilizados 50 baldes. Nota-se uma baixa concentração de píxeis próximos ao branco 
(intensidade 255) e alguns picos de ocorrência de cores bem próximas ao preto (intensidade 0). A maior concentração dos 
píxeis, entretanto, está nos tons intermediários, com valores de intensidade entre 100 e 200. No caso de imagens com mais
de uma compontente de cor (RGB, por exemplo), seriam gerados mais de um histograma, sendo um para cada componete.

Adotaremos a seguinte notação:

\begin{itemize}
 \item $H_x$ denota o histograma $x$;
 \item $N$ denota o total de baldes utilizados no histograma $x$;
 \item $H_{x}(i)$ denota o valor do balde $i$ do histograma $x$;
\end{itemize}

\subsection{Comparação de Histogramas} \label{sec:comparacao_histograma}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Em muitas situações, pode ser últil comparar histogramas a fim de se verificar a sua similiradade.
É razoável se pensar que um alto nível de semelhaça entre histogramas das componentes RGB de duas fotografias 
pode indicar, por exemplo, uma maior probabilidade de as imagens também serem semelhantes. Esta hipótese será 
explorada com maior profundidade nos capítulos seguintes.

Com a finalidade de se calcular a diferença entre dois histogramas, consideraremos 
três seguintes métodos nas subseções seguintes, a saber:

\begin{itemize}
	\item Correlação;
	\item Teste Chi-quadrado;
	\item Distância de Bhattacharyya.
\end{itemize}

Para a definição formal das técnicas mencionadas, introduzir-se-á a seguinte notação (em adição à notação 
previamente mencionada):

\begin{itemize}
	\item $m$ denota o método de comparação $m$, $m \in \{correlacao, chiquadrado, bhattacharyya\}$;
	\item $d_m(H_1,H_2)$ denota a diferença entre os histogramas $H_1$ e $H_2$ utilizando-se o método $m$;
	\item $\bar{H_{x}}$ denota a média de todos os $N$ baldes do histograma $x$.
\end{itemize}

\subsection{Comparação por Correlação} \label{sub:correlacao}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

A correlação é um método que indica a força e a direção do relacionamento linear entre duas 
variáveis aleatórias. A seguinte fórmula é utilizada para o cálculo da mesma:

\begin{equation}
  \rho(x,y)=
	\frac{cov(x,y)}{\sigma_{x}\sigma_{y}}=
	\frac{ E((x-\bar{x})(y-\bar{y})) }{\sigma_{x}\sigma_{y}}
\end{equation}

O coeficiente de correlação $\rho$ varia no intervalo
$\{-1,1\}$. Dizemos que a correlação é forte, se $\rho$ se aproxima de $1$ ou $-1$ e que é fraca se
ela se aproxima de zero. Além disso, sejam $x$ e $y$ variáveis aleatórias, denominamos a correlação de:

\begin{itemize}
	\item Perfeita positiva ($\rho=1$): $x$ varia exatamente na mesma proporção que $y$.
			 As variáveis são diretamente proporcionais, isto é, se $x$ aumenta em uma unidade, $y$
			 aumenta em uma unidade;
	\item Positiva ($0<\rho<1$): $y$ cresce na medida em que $x$ cresce, mas os valores não aumentam na mesma
			 proporção;
	\item Nula ($\rho=0$): neste caso, não existe relação entre os valores de $x$ e $y$;
	\item Negativa ($-1<\rho<0$): $y$ decresce na medida em que $x$ decresce, mas os valores não diminuem na mesma
			 proporção;
	\item Perfeita Negativa ($\rho=-1$): $x$ varia exatamente na mesma proporção que $y$, mas em sentido oposto.
			 As variáveis são inversamente proporcionais, isto é, se $x$ aumenta em uma unidade, $y$
			 diminui em uma unidade;
	\item Espúria: quando as variáveis são independentes, mas ainda assim o valor da correlação se distancia
			 de zero.
\end{itemize}

Os diagramas de dispersão da Figura~\ref{fig:correlacao_dispersao} ilustram os tipos de correlação:

\begin{figure}[H]
	\centering
	\includegraphics[width=0.7\textwidth]{imagens/capitulo2/correlacao_dispersao}
	\caption[Tipos de correlação legal.]{Tipos de correlação.}
	\label{fig:correlacao_dispersao}
\end{figure}

Por fim, apresentamos a fórmula que será utilizada para o cálculo do índice de correlação entre dois histogramas:

\begin{equation}
  d_{correlacao}(H_{a},H_{b})=
  \frac{\sum_{i=1}^{N}[(H_{a}(i)-\bar{H_{a}})
                       (H_{b}(i)-\bar{H_{b}})] 
       }
       {\sqrt{[\sum_{i=1}^{N}(H_{a}(i)-\bar{H_{a}})^2] 
              [\sum_{i=1}^{N}(H_{b}(i)-\bar{H_{b}})^2]}
       } 
\end{equation}


\subsection{Teste Chi-Quadrado e Distância de Bhattacharyya}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

O princípio básico dos testes de chi-quadrado é comparar proporções, isto é, se as frequências 
observadas se aproximam das esperadas para um certo evento. É um método muito útil para, por exemplo,
se determinar se uma moeda ou um dado são viciados. O coeficiente chi-quadrado ($\chi^{2}$) de 
Pearson é calculado pela fórmula

\begin{equation}
  \chi^{2}=
  \sum
			\frac{(f_{o}-f_{e})^2}
           {f_{e}}
\end{equation}

\noindent onde $f_{o}$ e $f_{e}$ representam, respectivamente, a frequência observada e esperada para cada classe.

No exemplo de um dado, se desejássemos verificar se ele está ou não viciado, cada face representaria 
uma classe com frequência esperada de $1/6$. O dado seria então lançado diversas vezes e os valores 
registrados para serem computados na fórmula. 

Observando a fórmula, vemos que se obtivéssemos o resultado
esperado para os lançamentos ($1/6$ de ocorrência de cada face), todos os $f_{o}$'s se cancelariam com os
$f_{e}$'s e o resultado seria zero. De maneira análoga, intuitivamente vemos que quanto mais os valores
observados se distanciam dos esperados, maior o valor do $\chi^{2}$.

Para aplicarmos o método à comparação de histogramas, assumimos que um dos histogramas ($H_{o}$) apresenta as 
frequências observadas e o outro ($H_{e}$) as frequências esperadas, empregando a seguinte fórmula: 

\begin{equation}
  d_{chi-quadrado}(H_{a},H_{b})=
	d_{chi-quadrado}(H_{e},H_{o})=
  \sum_{i=1}^{N}
			\frac{(H_{o}(i)-H_{e}(i))^2}
           {H_{e}(i)}
\end{equation}

Podemos observar pela fórmula que ocorre uma divisão por zero no caso do histograma apresentar algum
balde sem nenhuma ocorrência. O método da distância de Bhattacharyya elimina este problema,
além de fornecer resultados mais precisos do que o chi-quadrado para o caso de distâncias grandes.
O aprofundamento neste tópico foge ao escopo deste trabalho, mas um estudo detalhado sobre o assunto
pode ser encontrado em Thacker, Aherne e Rockett~\cite{bhattacharyya}.

A comparação entre os histogramas $H_{a}$ e $H_{b}$ por distância de Bhattacharyya é realizada através 
da seguinte fórmula:

\begin{equation}
	d_{bhattacharyya}(H_{a},H_{b})=
  \sqrt
	{
		1 -
		\frac{1}
         { \sqrt{ \bar{H_{a} } \bar{H_{b}} N^2 } }
		\sum_{i=1}^{N} \sqrt{ H_{a}(i) H_{b}(i) }
	}				
\end{equation}

Tanto o chi-quadrado quanto o bhattacharyya apresentam
resultado igual a zero no caso de histogramas iguais. Intuitivamente também podemos observar
que os valores tendem a aumentar na medida em que os histogramas se tornam mais diferentes.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Redes Neurais Artificiais} \label{secao_redes_neurais} %%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Existem na natureza inúmeros problemas difíceis de serem formulados como algoritmos~\cite{Kriesel2007NeuralNetworks}. 
Problemas que envolvem um número muito grande de variáveis tornam-se complexos e 
custosos. Um algoritmo criado especificamente para 
dirigir um carro automaticamente em uma rua movimentada, por exemplo, envolve condições 
adversas e pouco previsíveis, tornando sua 
implementação árdua. Entretanto, percebe-se que esta tarefa não é tão desafiadora 
para seres humanos. Isso se deve ao fato de
humanos terem um cérebro que consegue aprender.

Apesar de computadores terem, teoricamente, um poder de processamento muito 
maior do que o de um cérebro humano~\cite{Kriesel2007NeuralNetworks}, 
os dois normalmente trabalham de formas distintas. O sucesso das Redes Neurais 
A rtificiais (RNAs) consiste do fato de elas possuírem
características similares a de cérebros humanos, possuindo de certa forma a capacidade de aprender.

Como resultado desta capacidade, as redes neurais passam a ter o poder de 
generalizar e associar dados, de forma que, após serem treinadas, 
conseguem encontrar soluções para outros problemas da mesma classe, mas que não
foram vistos anteriormente~\cite{Kriesel2007NeuralNetworks}.

Encontram-se na literatura inúmeros modelos considerados RNAs. Devido ao seu 
poder de generalização, as aplicações destes algoritmos são inúmeras,
tendo atuação em áreas bastante distintas como física, ciência da computação, 
bioquímica, matemática, sociologia, economia, telecomunicações e 
várias outras~\cite{ANNForBeginers}.

Nos tópicos seguintes o termo Redes Neural Artificial será referido apenas como \textit{rede neural}, 
simplesmente \textit{rede} ou ainda de forma abreviada, \textit{RNA}.

\subsection{Visão Geral}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Uma rede neural é uma estrutura composta por unidades de processamento, chamados neurônios, 
interligados por conexões. Cada conexão possui um
peso que indica a importância do conteúdo que ela carrega. Diversos algoritmos 
foram desenvolvidos para realizar o balanceamento destes pesos
e várias funções foram criadas para processar as informações em cada neurônio, 
como será mostrado a seguir. Este balanceamento é chamado
\textit{treinamento} ou \textit{aprendizado}. A escolha destes algoritmos e 
funções dependem diretamente do problema em questão.

Definição: Uma rede neural é uma tripla ordenada (\textit{N,V,w}) 
com dois conjuntos \textit{N}, \textit{V} e uma função \textit{w}, aonde 
\textit{N} é um conjunto de neurônios e \textit{V} é o conjunto $\{(i,j)|i,j\in \mathbb{N} \}$ 
cujos elementos são denominados conexões
entre um neurônio \textit{i} e um neurônio \textit{j}. A função $w:V\to\mathbb{R}$ 
define os pesos, \textit{w}(\textit{i}, \textit{j}) 
representando o peso entre o neurônio \textit{i} e o neurônio \textit{j}~\cite{Kriesel2007NeuralNetworks}.

\subsection{Neurônio}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Cada neurônio recebe várias entradas de suas conexões (que podem ser dados 
de entrada da rede ou saídas de outros neurônios conectados a ele).
O processamento destas entradas é realizado por três funções: função de propagação $f_{prop}$, função de ativação $f_{ativacao}$,
função de saída $f_{saida}$, como ilustrado na Figura~\ref{fig:processamento_neuronio}.

\begin{figure}[H]
	\centering
	\includegraphics[width=0.5\textwidth]{imagens/capitulo2/processamento_neuronio}
	\caption[Processamento em um neurônio.]{Processamento em um neurônio~\cite{Kriesel2007NeuralNetworks}.}
	\label{fig:processamento_neuronio}
\end{figure}

A função de propagação é a responsável por processar o conjunto de entradas, juntamente com os pesos e condensar
esta informação em um valor escalar $e$. Normalmente utiliza-se esta função como a 
simples soma das multiplicações das entradas pelos os pesos, sendo 
esta a forma utilizada neste trabalho. Seja $I = \{i_{1},...,i_{n}\}$ o conjunto de entradas de um neurônio:

\begin{equation}
    f_{prop}(i_{1},...,i_{n}, w_{1},...,w_{n}) = \sum_{j = 0}^{n}i_{j} \cdot w_{j}
\end{equation}

A função de ativação $f_{ativacao}$ recebe como entrada o resultado da função de propagação $f_{prop}$. O seu papel é imitar o 
comportamento de ativação de um neurônio real, no qual acontecem reações químicas 
que definem se um impulso nervoso será transmitido
para os próximos neurônios (caso em que diz-se que o neurônio está \textit{excitado}) 
ou se o neurônio não enviará nenhum impulso 
nervoso. Para modelar este comportamento matematicamente, cria-se um limiar para cada neurônio. Se o valor de $f_{prop}$ exceder
este limiar, o neurônio é ativado e, caso contrário, ele fica inerte. Logo:

\begin{equation}
    a = f_{ativacao}(f_{prop}, \textit{limiar})
    \label{eq:f_ativacao}
\end{equation}

\noindent onde $e$ é o escalar calculado por $f_{prop}$ e $a$ é um valor que indica 
se o neurônio está ou não excitado. Como só existem duas opções
de saída para esta função (excitado ou não excitado), ela, idealmente, seria 
uma função booleana. Entretanto, para alguns algoritmos
de aprendizado, como o \textit{backpropagation}, é necessário que esta função 
seja diferenciável~\cite{Kriesel2007NeuralNetworks}. 
Desta forma, pode ser útil utilizar alguma função que aproxime este comportamento.
A Figura~\ref{fig:processamento_neuronio} apresenta a função booleana (não diferenciável) e
duas possíveis aproximações (diferenciáveis).

\begin{figure}[H]
	\centering
	\includegraphics[width=0.49\textwidth]{imagens/capitulo2/ativacao_booleana}
	\includegraphics[width=0.49\textwidth]{imagens/capitulo2/ativacao_hyperbolic_tg}
	\includegraphics[width=0.49\textwidth]{imagens/capitulo2/ativacao_fermi_function}
	
	\caption[Função booleana e duas possíveis aproximações.]{Função booleana e duas possíveis aproximações~\cite{Kriesel2007NeuralNetworks}.}
	\label{fig:funcoes_ativacao}
\end{figure}

A função de saída $f_{saida}$ é a responsável por enviar o resultado do processamento do neurônio para a sua saída, alimentando o
restante da rede. Pode-se realizar algum processamento com o resultado da ativação calculado pela $f_{ativacao}$, mas normalmente
utiliza-se apenas a função identidade, ou seja:

\begin{equation}
    f_{saida}(a) = a
    \label{eq:f_saida}
\end{equation}

Comumente, as funções de ativação e saída são definidas globalmente, ou seja, 
todos os neurônios possuem as mesmas funções. Entretanto,
pode-se criar conjuntos de neurônios com funções diferentes, dependendo do objetivo da 
aplicação~\cite{Kriesel2007NeuralNetworks}.

\subsection{Topologia}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Os neurônios de uma rede podem ser organizados e conectados de inúmeras maneiras. Para o contexto deste trabalho, entretanto,
será apresentada apenas um tipo de topologia, o \textit{Feedforward}.

Redes \textit{Feedforward} são organizadas em camadas de neurônios. Duas 
camadas sempre estarão presentes: a primeira camada, chamada
\textit{camada de entrada} e a última camada, chamada \textit{camada de saída}. 
Entre elas, podem existir \textit{n} outras camadas,
chamadas \textit{camadas escondidas}, invisíveis de fora da rede(\ref{fig:topologia}).
Neste tipo de topologia, cada neurônio apenas 
pode se ligar neurônios da próxima camada, de maneira que o sinal flui sempre da camada de entrada em 
direção a camada de saída. A camada de entrada é conectada diretamente com 
os \textit{inputs} da rede, de modo que apenas repassam
a informação a diante. Os únicos pesos não variáveis da rede são os pesos que ligam os \textit{inputs} à camada de entrada.

\begin{figure}[H]
	\centering
	\includegraphics[width=0.4\textwidth]{imagens/capitulo2/topologia}
	\caption{Camadas de uma rede neural.}
	\label{fig:topologia}
\end{figure}


Definir a quantidade de neurônios por camada 
não é uma tarefa simples. Normalmente utiliza-se na, camada escondida,
uma quantidade de neurônios menor ou igual a quantidade de neurônios na camada 
de entrada~\cite{IntroductionToNNJava}. A camada de saída é composta normalmente
por apenas um neurônio. Nesta camada, utilizam-se funções sigmóides como 
função de ativação quando o problema trata-se
de classificação, pois estas funções limitam os valores máximo e mínimo 
que a função pode retornar. Quando tratam-se de problemas de
regressão, utilizam-se funções lineares, pelo motivo contrário~\cite{NeuralNetworkMatlab}.

A Figura~\ref{fig:and_or} ilustra os conceitos abordados até o momento por meio de duas possíveis topologias 
para redes simples que modelam as portas lógicas E e OU. 
No exemplo, a camada de entrada recebe valores binários 
(1 ou 0, sendo uma entrada para cada neurônio) e apenas repassa a 
informação adiante, ou seja, sua função de ativação é a função identidade. O número 1 nas arestas 
indica o peso da conexão e os números 1.5 e 0.5 nos neurônios da segunda camada indicam seus limiares. 
É possível utilizar o limiar de cada neurônio como um peso, de forma que ele também possa ser 
ajustado~\cite{Kriesel2007NeuralNetworks}. Desta forma, a mesma topologia pode ser adaptada para aproximar as duas funções. 

\begin{figure}[H]
	\centering
	\includegraphics[width=0.8\textwidth]{imagens/capitulo2/and_or}
	\caption[Redes \textit{Feedforward} simples das funções E e OU, respectivamente.]{Redes \textit{Feedforward} simples das funções E e OU, respectivamente~\cite{Kriesel2007NeuralNetworks}.}
	\label{fig:and_or}
\end{figure}

Na camada de saída, a função de propagação multiplica as entradas pelos pesos e faz o somatório deste resultado.
A função de ativação é uma função booleana que retorna 1 se o resultado 
da função de propagação for maior do que o limiar e 0 caso contrário.
Observa-se que com esta configuração, cada uma das redes resulta na saída correta para cada uma das funções.

Exemplificando para a função E:

\begin{equation}
\begin{split}
    1 \cdot w_{1} + 1 \cdot w_{2} > 1.5.\ Resultado: 1 \\
    1 \cdot w_{1} + 0 \cdot w_{2} < 1.5.\ Resultado: 0 \\
    0 \cdot w_{1} + 1 \cdot w_{3} < 1.5.\ Resultado: 0 \\
    0 \cdot w_{1} + 0 \cdot w_{4} < 1.5.\ Resultado: 0 \\
\end{split}
\end{equation}

Aonde $w_{1}$ e $w_{2}$ tem sempre o valor 1. Este exemplo simples mostra que é possível aproximar uma função 
apenas modificando os pesos das conexões entre neurônios.

\subsection{Paradigmas de Aprendizado}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Existem 3 principais paradigmas de aprendizado:

\begin{itemize}
    \item Aprendizado \textit{supervisionado};
    \item Aprendizado \textit{não-supervisionado};
    \item Aprendizado \textit{por reforço}.
\end{itemize}

Sistemas de aprendizado supervisionado tem por objetivo a elaboração 
de uma função de mapeamento a partir de um treinamento prévio. 
O sistema é treinado com uma série de \textit{inputs} rotulados, isto é, cuja resposta é conhecida. 
A tarefa do algoritmo passa a 
ser predizer os resultados de uma entrada desconhecida, dado que ele já analisou vários exemplos anteriormente. Poderíamos dizer 
que o aprendizado supervisionado é algo como aprender por exemplos. 
Existem, portanto, ao menos duas etapas: a de treinamento e a 
de predição.

De maneira mais formal, o objetivo do aprendizado supervisionado é 
construir uma função $g=(x,f(x))$ que irá aproximar a função $f$, não conhecida,
onde x é a variável que representa os \textit{inputs} válidos e $f(x)$ a resposta conhecida. Quando $f$ é uma função contínua, 
diz-se que $g$ trata-se de uma regressão, enquanto que quando os 
\textit{outputs} de $f$ são discretos, diz-se que é um problema de
classificação. Um \textit{software} de detecção de faces poderia ser 
implementado, por exemplo, com um sistema supervisionado no qual
imagens rotuladas como "rosto" ou "não-rosto" seriam fornecidos como 
treinamento. Informações como "aspecto redondo", "discos escuros
nos locais dos olhos", etc., poderiam tentar definir como um rosto se 
parece, mas estes dados não estariam codificados no programa.
O sistema iria tentar, com base apenas nos exemplos do treinamento, 
decidir como um rosto se parece e inferir quais figuras 
tratam de faces e quais não.

No contexto deste trabalho, será abordado apenas o aprendizado \textit{supervisionado}. 
Os outros dois paradigmas diferenciam-se principalmente
por não possuírem os rótulos, ou pelo o menos, não todos eles, de forma 
que não se conhece, a princípio, a saída correta.

Um sistema de aprendizado se auto modifica para se adaptar a mudanças 
no ambiente~\cite{Kriesel2007NeuralNetworks} e assim aproximar
a função $f$ não conhecida. Em uma rede neural, esta modificação do sistema pode 
ocorrer de várias maneiras:

\begin{itemize}
    \item Modificar os pesos de cada neurônio;
    \item Criar novas conexões entre neurônios;
    \item Apagar conexões entre neurônios;
    \item Modificar os valores de \textit{limiar};
    \item Criar novos neurônios;
    \item Apagar neurônios;
    \item Variar as funções de propagação, ativação e/ou saída.
\end{itemize}

No caso deste trabalho, será abordada apenas a primeira forma de adaptação, modificando os pesos de cada conexão.

\subsection{Medidas de Erro}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

O erro é uma função que calcula a distância entre os valores esperados e os valores atuais obtidos pela rede.
No contexto deste trabalho, o erro é uma função dos pesos, já que eles são as únicas variáveis presentes no sistema. Seja $W$ um
vetor contendo os pesos de todos os neurônios, temos $Err:W\to\mathbb{R}$. Normalmente, utiliza-se esta função
como sendo o erro mínimo quadrático:

\begin{equation}
    Err(W) = (f_{saida}(a) - k)^2
\end{equation}

Onde $k$ é o valor da saída esperada para um determinado neurônio 
e $a$ e $f_{saida}$ são definidos nas equações~\ref{eq:f_ativacao} e ~\ref{eq:f_saida}.

O objetivo do sistema é minimizar o erro, de forma a ajustar os pesos 
para que as saídas da rede estejam suficientemente próximas 
das saídas corretas. Para alcançar este objetivo, utiliza-se o gradiente 
descendente da função de erro, que tenta minimizar a função
de erro (podendo chegar a um mínimo local ou a um mínimo global)~\cite{Kriesel2007NeuralNetworks}. 
Desta forma, deseja-se modificar os valores dos pesos de forma que o erro diminua. A variação dos
pesos, $\Delta W$, pode ser 
definida genericamente como:

\begin{equation}
    \Delta W \sim - \nabla Err
\end{equation}

A rede modificará então seus pesos de maneira a minimizar o erro. A cada 
novo ajuste dos pesos, dá-se o nome de \textit{epoch},
ou etapa de treinamento. A cada nova etapa, calcula-se novamente o erro 
e modifica-se novamente os pesos, até que algum critério de
parada seja atingido. 

\begin{figure}[H]
	\centering
	\includegraphics[width=0.49\textwidth]{imagens/capitulo2/superficie_erro}
	\includegraphics[width=0.49\textwidth]{imagens/capitulo2/gradiente}
	\caption[Superfície de Erro e Gradiente Descendente.]{Superfície de Erro e Gradiente Descendente~\cite{Kriesel2007NeuralNetworks}.}
	\label{fig:superficie_erro_gradiente}
\end{figure}

A Figura~\ref{fig:superficie_erro_gradiente} mostra, à esquerda, 
um exemplo de superfície de erro para uma rede com duas conexões. Ao lado 
da superfície, é apresentado um exemplo do comportamento do gradiente 
descendente. Observa-se que seu valor sempre muda em direção ao menor 
valor da função, de modo que pode ficar estagnado em um mínimo local. 

Além do gradiente descendente, pode-se utilizar o algoritmo 
Levenberg-Marquardt \cite{levenbergMarquardt} para melhorar a 
performance do treinamento no que diz respeito ao tempo de convergência. Da mesma forma que o gradiente, ele provê uma solução 
para o problema de minimização de uma função não-linear. Pode ser aplicado para o treinamento de redes neurais jutamente com o 
\textit{backpropagation} e é adequado para problemas de tamanho pequeno e médio.

O erro global pode ser obtido somando-se os erros de cada neurônio.


%O balanceamento dos pesos da rede é feito a partir de uma medida da distância entre os valores obtidos e os valores esperados.
%A esta distância, dá-se o nome de \textit{erro} e pode ser medida de diferentes formas dependendo do algoritmo de aprendizado.
%A partir deste cálculo, tenta-se decidir quais valores de pesos seriam melhores para diminuir esta distância, chegando a valores
%mais próximos dos valores esperados de saída.

%Este procedimento de cálculo de distância e ajuste dos pesos é chamado de \textit{epoch}. Espera-se que a cada \textit{epoch},
%a saída da rede se torne mais próxima da saída esperada.

%Dependendo da complexidade do problema, pode ser que, após várias \textit{epochs} o sistema não consiga mais diminuir a taxa
%de erro. Por outro lado, pode-se obter uma taxa de erro tão pequena que ocorra um \textit{overfitting}, ou seja, o sistema memorizou
%as saídas a partir das entradas, perdendo poder de generalização. Ambos os problemas indicam que existe uma hora certa de se
%parar o treinamento.

\subsection{\textit{Perceptron} e \textit{Backpropagation}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Em 1958, Rosenblatt~\cite{rosenblatt58} propôs o \textit{Perceptron} como o primeiro modelo de aprendizagem de RNAs
utililzando a abordagem supervisionada. Originalmente foi concebido como uma rede \textit{Feedforward} com apenas as
camadas de entrada e de saída, sem nenhuma camada oculta, sendo uma das formas mais simples de RNA. 
O Perceptron utiliza como algoritmo de aprendizado a chamada Regra Delta~\cite{rosenblatt1962principles} que, de acordo
com o Teorema da Convergência do Perceptron, sempre converge se, e somente se, os dados utilizados para treinamento forem 
linearmente separáveis. As redes E e OU apresentadas da seção anterior podem ser implementadas
como Perceptrons.

\begin{figure}[]
	\centering
	\includegraphics[width=0.35\textwidth]{imagens/capitulo2/linearly_separable_data}
	\includegraphics[width=0.35\textwidth]{imagens/capitulo2/nonlinearly_separable_data}
	\caption[Padrões separáveis e não-separáveis linearmente.]{Padrões separáveis e não-separáveis linearmente~\cite{MachineLearning}.}
	\label{fig:superficie_erro_gradiente}
\end{figure}

Esta característica de conseguir encontrar apenas padrões linearmente separáveis resultou, por muitos anos, em um grande
desinteresse da comunidade científica pela continuidade de pesquisas em redes neurais, de modo que uma solução para este
problema só veio a ser proposta em meados da década de 1980. 

Em 1986 descobriu-se que problemas não separaveis linearmente poderiam ser resolvidos por Perceptrons de múltiplas
camadas utilizando o algoritmo de \textit{retropropagação de erro}, conhecido 
como \textit{Backpropagation}~\cite{Kriesel2007NeuralNetworks}.

\subsection{Critérios de Parada}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Não é uma tarefa simples decidir quando parar o algoritmo de aprendizado. Pode-se definir critérios simples
como a quantidade máxima de iterações, ou um valor limite mínimo para a o erro global da rede.

Outra forma de se definir um critério de parada é utilizando um conjunto de validação. Durante o treinamento, 
utiliza-se um conjunto que não é utilizado para balancear os pesos e monitora-se o erro deste conjunto.
Este erro de validação normalmente vai diminuindo na etapa inicial do treinamento. Entretanto, quando a rede
começa a se ajustar aos dados de entrada (do conjunto de treinamento), ela começa a se tornar \textit{superajustada},
perdendo capacidade de generalização. Neste ponto, o erro de validação para de diminuir, começando a aumentar
indicando um bom momento para se parar o treinamento~\cite{NeuralNetworkMatlab}.

Normalmente todos os critérios de parada são utilizados em conjunto, de forma que o treinamento é interrompido
quando algum deles for atingido.


